package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-16 16:57
 */
public class OneSum {
    public static void main(String[] args) {

    }
    //思路：对于数组和strs而言，满足条件的0和1个数的字符串有哪些取决于

    /**LeetCode 474
     * 动规五部曲：1.dp[i][j],i和j分别代表1和0的个数，dp[i][j]代表满足当前情况的最多的字符串的个数
     * 2.递推公式：dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1;3.初始化dp[0][0]=1;4.遍历顺序，一层是数组，二三层是容量，容量从大到小遍历
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public static int oneNum(String[] strs,int m,int n){
        //创建dp
        int[][]dp=new int[m+1][n+1];

        for (String element:strs) {
            for(int i=0;i<element.length();++i){
                int x=0;//记录1的个数
                int y=0;//记录0的个数
                if (element.charAt(i)=='0'){
                    x++;
                }else{
                    y++;
                }
                //二层循环
                for(int j=m;j>=x;--j){
                    for(int k=n;k>=y;--k){
                        dp[j][k]=Math.max(dp[j][k],dp[j-x][k-y]+1);
                    }
                }
            }
        }
        return dp[m][n];
    }
}
